package binaryTree;

import org.junit.Test;

/*
 *@description N 皇后 II
 *@author hkfan
 *@version 1.0
 *@create 2025/6/16 15:36
 */
public class LeetCode_52 {

    @Test
    public void test(){
        System.out.println(totalNQueens(2));
    }

    public int totalNQueens(int n) {
        int[][] grid = new int[n][n];
        solution(grid,0,n);
        return res;
    }

    int res = 0;

    private void solution(int[][] grid, int i, int n) {
        if (i==n){
            res++;return;
        }
        for (int j = 0; j < n; j++) {
            if (check(grid,i,j)){
                grid[i][j]=1;
                solution(grid,i+1,n);
                grid[i][j]=0;
            }
        }
    }

    private boolean check(int[][] grid, int row, int col) {
        for (int i = 0; i <= row; i++) {
            for (int j = 0; j < grid.length; j++) {
                if ((!(i==row&&j==col)) && grid[i][j]==1 && ((i==row)||(j==col)||(i-row==j-col)||(i-row==col-j))){
                    return false;
                }
            }
        }
        return true;
    }
}
